package offer;

/**
 * @Author SSK
 * @Date Created in 18:47 2019/8/8
 * @Description 数据流中的中位数
 * @Version 1.0
 */
public class T64 {

    class AVL {
         private TreeNode root ;
         public class TreeNode {
            public TreeNode left;
            public TreeNode right;
            public int val;
            public int hight;
            public int childrenNum;
            public TreeNode() {
                 hight = 1;
                 childrenNum = 1;
            }
            public TreeNode(int val) {
                this();
                this.val = val;
            }

         }
         private int getHight(TreeNode treeNode) {
             if (treeNode==null) {
                 return 0;
             }
             return treeNode.hight;
         }
        private int getChildrenNum(TreeNode treeNode) {
            if (treeNode==null) {
                return 0;
            }
            return treeNode.childrenNum;
        }
        private void update(TreeNode treeNode) {
            treeNode.hight = Math.max(getHight(treeNode.left),getHight(treeNode.right)) + 1;
            treeNode.childrenNum = getChildrenNum(treeNode.left) + getChildrenNum(treeNode.right) + 1;
        }
         private TreeNode rotateLeft(TreeNode treeNode) {
             TreeNode rightNode = treeNode.right;
             treeNode.right = rightNode.left;
             rightNode.left = treeNode;
             update(treeNode);
             update(rightNode);
             return rightNode;
         }
        private TreeNode rotateRight(TreeNode treeNode) {
             TreeNode leftNode = treeNode.left;
             treeNode.left = leftNode.right;
             leftNode.right = treeNode;
             update(treeNode);
             update(leftNode);
             return leftNode;
         }
         public TreeNode treeLeftLeft(TreeNode treeNode) {
             return rotateRight(treeNode);
         }
         public TreeNode treeRightRight(TreeNode treeNode) {
            return rotateLeft(treeNode);
         }
         public TreeNode treeLeftRight(TreeNode treeNode) {
             treeNode.left = rotateLeft(treeNode.left);
             return rotateRight(treeNode);
         }
        public TreeNode treeRightLeft(TreeNode treeNode) {
            treeNode.right = rotateRight(treeNode.right);
            return rotateLeft(treeNode);
        }
         public void insert(int x) {
             root = insert(x,this.root);
         }
         private TreeNode insert(int x,TreeNode treeNode) {
             if (treeNode==null) {
                 return new TreeNode(x);
             }
             if (x > treeNode.val) {
                   treeNode.right = insert(x,treeNode.right);
                   if (getHight(treeNode.left)-getHight(treeNode.right)==-2) {
                        if (x > treeNode.right.val) {
                            treeNode = treeRightRight(treeNode);
                        } else {
                            treeNode = treeRightLeft(treeNode);
                        }
                   }
             } else {
                 treeNode.left = insert(x,treeNode.left);
                 if (getHight(treeNode.left)-getHight(treeNode.right)==2) {
                     if (x <= treeNode.left.val) {
                         treeNode = treeLeftLeft(treeNode);
                     } else {
                         treeNode = treeLeftRight(treeNode);
                     }
                 }
             }
             update(treeNode);
             return treeNode;
         }
         public TreeNode getThTree(int x) {
             TreeNode treeNode = root;
             while (true) {
                 if (x>=getChildrenNum(treeNode.left)+1) {
                     x-=getChildrenNum(treeNode.left)+1;
                     if (x==0)  {
                         return treeNode;
                     }
                     treeNode = treeNode.right;
                 } else {
                     treeNode = treeNode.left;
                 }
             }

         }
         public void print(TreeNode node) {
              if (node==null) {
                  System.out.print(" # ");
                  return;
              }
              System.out.print(" "+node.val+" ");
              print(node.left);
              print(node.right);
         }
         public int getTreeNodeNum() {
             return root.childrenNum;
         }
         public Double GetMedian() {
             if (getChildrenNum(root)%2==1) {
                 return getThTree(getChildrenNum(root)/2+1).val*1.0;
             }
             return (getThTree(getChildrenNum(root)/2).val+getThTree(getChildrenNum(root)/2+1).val)*1.0/2;
         }


    }

    public AVL avl = new AVL();
    public void Insert(Integer num) {
        avl.insert(num);
    }

    public Double GetMedian() {
        return avl.GetMedian();
    }
    public static void main ( String[] args) {
        int[] array = new int[]{5,2,3,4,1,6,7,0,8};
        T64 t64 = new T64();
        for (int i = 0; i < array.length; i++) {
            t64.Insert(array[i]);
            System.out.println(t64.GetMedian());
        }

    }
}
